
typedef struct {
    int top;
    int *nums;
} stack_t;

typedef struct {
    stack_t *stack_out;
    stack_t *stack_in;
} MyQueue;

// 维护两个栈，输入栈，输出栈
// 入队操作：元素直接放到stack_in（不考虑stack_int满，而stack_out有数据的情况）
// 出队操作：如果stack_out不空，直接出栈；否则先将stack_in中所有元素弹入stack_out，再出栈
void stack_init(stack_t **s, int size) {
    *s = malloc(sizeof(stack_t));
    (*s)->top = -1;
    (*s)->nums = malloc(sizeof(int)*size);
}
int is_empty(stack_t *s) {
    return (s->top == -1);
}
void push(stack_t *s, int value) {
    s->nums[++s->top] = value;
}
int pop(stack_t *s) {
    return s->nums[s->top--];
}
int top(stack_t *s) {
    return s->nums[s->top];
}


/** Initialize your data structure here. */
#define STACK_SIZE 100
MyQueue* myQueueCreate() {
    MyQueue *q = malloc(sizeof(*q));
    stack_init(&q->stack_in, 100);
    stack_init(&q->stack_out, 100);
    return q;
}

/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x) {
    push(obj->stack_in, x);
}

/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {
    if (is_empty(obj->stack_out)) { //输出栈空时，将输入栈中的所有元素弹入输出栈
        while (!is_empty(obj->stack_in)) {
            push(obj->stack_out, pop(obj->stack_in));
        }
    } 
    return pop(obj->stack_out);
}

/** Get the front element. */
int myQueuePeek(MyQueue* obj) {
    if (!is_empty(obj->stack_out)) return top(obj->stack_out);
    else return obj->stack_in->nums[0];
}

/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue* obj) {
    if (is_empty(obj->stack_out) && is_empty(obj->stack_in)) return true;
    else return false;
}

void myQueueFree(MyQueue* obj) {
    free(obj->stack_in->nums);
    free(obj->stack_in);
    free(obj->stack_out->nums);
    free(obj->stack_out);
    free(obj);
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/